#include <iostream>
using namespace std;

//折半查找
template <typename E>
int BinarySearch(E a[], int n, E x)
{
    int low = 0, high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(a[mid] == x)
            return mid;
    else if(x < a[mid])
        high = mid - 1;
    else
        low = mid + 1;
    }
    return -1; //未找到
}

template <typename E>
int BinarySearch(E a[], int low, int high, E x)
{
    if(low > high) return -1;

    int mid = (low + high) / 2;
    if(a[mid] == x)
        return mid;
    else if(x < a[mid])
        return BinarySearch(a, low, mid - 1, x);
    else
        return BinarySearch(a, mid + 1, high, x);
}

int main()
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    cout << BinarySearch(a, 10, 1) << endl;
    cout << BinarySearch(a, 10, 8) << endl;
    cout << BinarySearch(a, 10, 12) << endl;
    cout << BinarySearch(a, 0, 9, 1) << endl;
    cout << BinarySearch(a, 0, 9, 8) << endl;
    cout << BinarySearch(a, 0, 9, 12) << endl;

}